分散リソース管理のためのバランスしたコンシステント・ハッシュ

专利摘要:
クラスタのようなマルチコンピュータ環境内のリソース管理責任のバランスし調和した配置のための、方法、システム、コンピュータ読み取り可能な記憶媒体及び装置を提供するものであり、クラスタリソースの効率的使用をなし、スケーラブルにするものである。実施例では、生き残るクラスタメンバー間でのリソース管理責任の再分散量を減ずることにより、リソース管理責任の再分散のためにクラスタが利用不能となる時間を減少させる。実施例では、更に、複数の残りのクラスタノードの相対的能力に基づきリソース管理責任の再分散を提供する。
公开号:JP2011510367A
申请号:JP2010540865
申请日:2008-12-23
公开日:2011-03-31
发明作者:ウォン，カイ・シウ；クマレサン，バラ；プリンス，ハロルド・ビイ・ジェイアール
申请人:シマンテック コーポレーションＳｙｍａｎｔｅｃ Ｃｏｒｐｏｒａｔｉｏｎ；
IPC主号:G06F12-00

专利说明:

[0001] 本発明は、コンピュータリソース管理に関し、特に、多数のコンピュータからなるネットワークにおいてリソース管理責任を分散するシステムおよび方法に関する。]
背景技術

[0002] 情報、および、情報を生成し、分配し、該情報を様々な形態で維持するコンピューティングシステムに対する高まっている依存により、情報リソースおよびこれらの情報リソースに対するアクセスを提供するための技術に対する大きな需要が継続している。多くの企業および団体は、かなりの量のコンピューティングリソース（コンピュータ資源）のみならず、最小のダウンタイムで利用可能なリソースを必要としている。このような要求に対する解決策の1つは、コンピューティングリソースがクラスタ化され、これにより、記憶領域ネットワーク環境における共有データにアクセスするための融通性があり、高性能で可用性が高いプラットフォームを提供する環境である。クラスタ全体のボリュームおよびファイルシステム構成は、簡略化され集中化された管理を可能にする。追加的な効果は、クラスタにおけるすべてノードに対して、共用化された装置構成の同じ論理的ビュー（仮想テーブル）を提供する一体化されたクラスタボリュームマネージャが提供されることである。]
[0003] クラスタ環境の利点は、情報アクセスについての単一障害点を除去しまたは実質的に減少させる能力である。前記クラスタにおけるすべてのコンピュータノードは、共用されるデータリソースの同じビューが与えられ、同じ態様でこれらのデータリソースにアクセスすることができる。従って、1または複数の前記コンピュータリソースが故障に見舞われると、該故障したシステムによって実行されているタスクは、他のコンピュータノードに移されて更なる処理を受けることができる。クラスタリソース管理について単一障害点の除去または減少を効果的に実現するために、管理は前記クラスタのメンバーノード間で分散される。]
[0004] クラスタのメンバーが該クラスタを離れると、該メンバーのリソース管理責任を残りのクラスタメンバー間で分散させる手配がなされなければならない。このようなリソース管理責任の再分散は、計算サイクルおよびネットワーク帯域等の、クラスタリソースを効率的に利用する態様で実行される、ことが望ましい。さらに、このようなリソース管理責任の再分散は、残りのクラスタメンバーの相対的能力を考慮することが望ましい。また、クラスタメンバー間のリソース管理責任の再分散の効率において、残りのノード間でのリソース管理責任の変動が最小化されることが望まれる。]
[0005] 本発明は、クラスタのようなマルチコンピュータ環境内のリソース管理責任のバランスし調和した配置のための仕組みを提供するものであり、クラスタリソースの効率的使用をなし、スケーラブルにする（拡張性をもたせる）ものである。本発明の実施例は、生き残るクラスタメンバー間でのリソース管理責任の再分散量を減ずることにより、リソース管理責任の再分散のためにクラスタが利用不能となる時間を減少させる。本発明の実施例は、複数の残りのクラスタノードの相対的能力に基づきリソース管理責任の再分散を提供する。]
[0006] 本発明の一実施例では、リソース識別空間における複数のリソース識別子の配置（location：所在位置）が判定され、該リソース識別空間は複数の責任領域に分割され、各責任領域の管理責任が対応するネットワークノードに割り当てられる。上記実施例の一観点においてリソース識別空間は名前空間（name space）であり、更なる観点において該名前空間内の格納位置を決定するためにリソースの名前がハッシュ（hash）される。上記実施例の別の観点において、リソース識別空間の前記領域に対する責任が割り当てられるネットワークノードは、ネットワークノードのクラスタのメンバーである。上記実施例の更に別の観点において、責任の範囲のサイズは該割り当てられたネットワークノードの相対的能力によって決定される。上記実施例の別の観点において、ネットワークの取り外し又は追加によって、利用可能なノードの数が変動するとき、リソースの管理責任は、ネットワークノード間でのリソース管理責任の再分散を最小化することを見つけ出すような手法で、再分散化される。]
[0007] 添付図面を参照することにより、本発明がより良く理解され、かつ、その目的、特徴、及び利点が当業者にとって明瞭にされるであろう。]
図面の簡単な説明

[0008] 本発明の実施例を具現化するのに適したマルチコンピュータ・ネットワーク・クラスタ構成を簡略化して示すブロック図。]
[0009] 本発明の実施例によって使用可能な、分散ロックマネージャを提供する２つのレベルのロックマネージャ環境を簡略化して示すブロック図。]
[0010] ロックマスターが１クラスタ内の様々なノード間でどのように分散されるかを示す図。]
[0011] 本発明の実施例に従い、よって使用可能な、分散ロックマネージャを提供する２つのレベルのロックマネージャ環境を簡略化して示す図。]
[0012] 本発明の実施例に従い、マッピングテーブル再構築プロセス中にクラスタノードによって実行されるタスクの一実施例を簡略化して示すフロー図。
本発明の実施例に従い、マッピングテーブル再構築プロセス中にクラスタノードによって実行されるタスクの一実施例を簡略化して示すフロー図。]
[0013] 本発明の実施例に従い、クラスタ環境におけるプロキシと再配置されたマスターとの間のリマスター（remaster: マスター組み直し）メッセージのやり取りを簡略化して示すブロック図。]
[0014] 本発明の実施例に従い、ロックマスター再分散化中に複数クラスタノードについての新たなマスターをセットアップする場合に実行さるいくつかのタスクを簡略化して示すフロー図。]
[0015] 本発明の実施例を実装するのに適したコンピュータシステムを示すブロック図。]
[0016] 本発明の実施例を実装するのに適したネットワークアーキテクチャを図示するブロック図。]
実施例

[0017] 本発明は、クラスタのようなマルチコンピュータ環境内のリソース（資源）管理責任のバランスし調和した配置（balanced and consistent placement）のための仕組みを提供するものであり、クラスタリソースの効率的使用をなし、スケーラブルにする（scalable:拡張性をもたせる）ものである。本発明の実施例は、生き残るクラスタメンバー間でのリソース管理責任の再分散量を減ずることにより、リソース管理責任の再分散のためにクラスタが利用不能となる時間を減少させる。本発明の実施例は、複数の残りのクラスタノードの相対的能力に基づきリソース管理責任の再分散を提供する。]
[0018] クラスタ環境及び分散ロック
図１は、本発明の実施例を具現化するのに適したマルチコンピュータ・ネットワーク・クラスタ構成を簡略化して示すブロック図である。クラスタ１２０は、該クラスタのメンバーである複数のコンピュータノード（compute node：計算ノード）１１０（１）〜１１０（ｎ）を含む。コンピュータノード１１０（１）〜１１０（ｎ）はネットワーク１２０によって結合されている。図示するように、コンピュータノード１１０（１）〜１１０（ｎ）は、記憶ボリュームリソース１４０（１）〜１４０（ｎ）へのアクセスを提供する記憶エリアネットワーク（ＳＡＮ）１３０にも接続されている。別の例として、記憶リソースは、バスベースのコントローラを介して様々なコンピュータノードに直接的に結合されることができ、あるいは、例えばネットワークアクセス可能な記憶装置として結合されることができる。各コンピュータノード１１０（１）〜１１０（ｎ）はＳＡＮ１３０の記憶プールへの同時アクセスを持つ。この記憶リソースへの同時アクセスが与えられたならば、データの完全さを保証するために記憶プールへの読み書きアクセスを調整する必要がある。] 図１
[0019] 図１に示すようなクラスタ環境においては、多様なリソースが該クラスタのメンバーノードによって共有される。そのようなリソースはＳＡＮ１３０内の記憶リソースを含み得、アプリケーションはクラスタの様々なメンバーノード上で実行され得、その他も同様である。クラスタのメンバーノード間のそのようなリソースの管理の分散は、それらのリソースへのアクセスの利益を受けることができない単一ポイントの存在を無くす若しくは減少する。] 図１
[0020] クラスタ内のリソースへのアクセスを管理する一例は、ＳＡＮ１３０の記憶リソースによって提供されるクラスタファイルシステムに関連付けられたファイルロック（file lock）アーキテクチュアである。クラスタファイルシステムはクラスタ内の全てのファイルの単一のバージョンを提供し、それは該クラスタ内の全てのノードが見えるようになっている。各メンバーノードが或る特定のファイルについてそれ自身のバージョンを持っているとすると、特に該ファイルに対する書き込みアクセス中に、いずれか１ノードの所有するものが間違った情報となる可能性がある。特定のデータに対するいずれの書き込みアクセス中に該データの単一バージョンだけが存在することを保証するために、ファイルロック処理がクラスタ全体のファイルシステムにおいて実行される。]
[0021] 単一のコンピュータシステム内において、所与のソフトウェアアプリケーションを実行している複数のスレッドが同じデータにアクセスあるいはアップデートしてよい。「スレッド」という用語は、コンピュータプログラムが実行しているコンテキストを記述するために使用される。スレッド間の調整は、或るスレッドがデータをアップデートしているときは、２つの操作のタイミングに依存するデータの非調和がもたらされる可能性があるので、別のスレッドが共有データを読まないようにする、ということを保証するために必要である。図１に示すようなクラスタ環境においては、所与のソフトウェアアプリケーションの処理が様々なメンバーノード間で負荷バランスされ得る場合、データを共有する複数スレッドが該クラスタ内の異なるノード上で実行され続け得る。] 図１
[0022] 共有データにアクセスする複数スレッド間の調整は、ロック処理を使用して実現できる。典型的には、ロックとは、共有データの１ピース例えば１ファイル又は１ディスクブロックを保護することである。クラスタのような分散システムにおいて、ロックは、所与のソフトウェアアプリケーションのオンライン又はオフラインステイタスのような、該システムの各ノードのメモリ内に分散された共有の「状態」情報、を保護することもできる。全ての共有データはロックによって保護され、ロックは典型的にはロックマネージャによって管理される。ロックマネージャは該データにアクセスする別のアプリケーションプログラムによって使用されるべきインタフェイスを提供する。]
[0023] データに対するロックは、呼び出しするアプリケーションプログラムが該ロックによって保護されるデータにアクセスできる前に、リクエストされる。呼び出しするアプリケーションプログラムは典型的には、該ロックによって保護されるデータを書き込む又はアップデートするための「排他的」ロック、若しくは、該ロックによって保護されるデータを読み取るための「共有」ロックをリクエストする。呼び出しするアプリケーションが排他的ロックを許すならば、ロックマネージャは呼び出しするプログラムが該ロックを保持している１つのスレッドだけであることを保証する。呼び出しするアプリケーションが共有ロックを許すならば、別のスレッドが該データについての共有ロックを保持していてよく、しかし、該データについての排他的ロックは保持できない。]
[0024] ロックマネージャはロックリクエストをすぐに許可することができない。１つのスレッドが所与のデータセットについての排他的ロックＬを持ち、第２のスレッドが該所与のデータセットに対して共有されたアクセスをリクエストすることを一例として考えてみる。該第２のスレッドのリクエストは、第１のスレッドが該所与のデータセットについての排他的ロックを解除してしまうまで、許可されることができない。]
[0025] ロックは、ＳＡＮ１３０を通してアクセス可能なボリュームのような共有ディスク上に格納されるデータに置かれる。ロックは、データがクラスタ内の全てのノードについて一致されねばならない場合には、各ノードごとのメモリ内に格納された共有データに置かれることもできる。例えば、クラスタ内のノードはファイルシステムが搭載されたことを示す情報を共有することができる。ロックはファイルシステムの状態が搭載から不搭載に変わるとき又はその逆のとき、共有状態情報に置かれる。]
[0026] 分散ロック管理
上述のように、ロックマネージャはロック処理によって保護されたデータにアクセスするためのリクエストに応答する。クラスタ環境において、ロックマネージャのようなリソースマネージャは、単一ポイントでの失敗が無いようにする又は減ずるために、クラスタのメンバーノード間で分散化されることが望まれる。]
[0027] 図２は本発明の実施例によって使用可能な、分散ロックマネージャを提供する２つのレベルのロックマネージャ環境を簡略化して示すブロック図である。例えば、ノード２１０内のクライアントスレッド２１５はプロキシ２２０（Ａ）を通してロックＡをリクエストする。そのようなシステムにおいて、ロックを保持又はリクエストするノード毎のロック毎に１つのプロキシがある。例えば、ノード２４０上のロックＡを保持又はリクエストするクライアント２４５に対応する該ノード２４０（プロキシ２５０（Ａ））上の該ロックＡのためのプロキシも有り得る。しかし、もしノード２４０がすでにロックＡへのアクセスをしていないならば、プロキシ２５０（Ａ）はロックＡ用のマスターに該ロックＡをリクエストするであろう。図２に示すように、ロックＡ用のマスターは、ノード２１０に所在するマスター２３０（Ａ）である。クラスタ内のロックにつき１つのマスターがある。もし該マスターがリクエストしているスレッドを実行しているノードに所在していないならば、該ノードに在るマスターテーブルが、リクエストされたロックにマスターを提供する遠隔のノードがどれであるか（識別）を見つけるために、参照される。例えば、もしクライアントがノード２１０上のプロキシ２２０（Ｃ）にロックＣをリクエストしたならば、該プロキシ２２０（Ｃ）はノード２７０上のロックＣのマスター２９０（Ｃ）にロックＣをリクエストするであろう。ノード２１０が別の異なるスレッドのためにロックＡを許可されてしまったとすると、プロキシ２２０（Ｃ）は、ロックマスターに更にリクエストすることなく、リクエストしているクライアントに対してロックＣを分散化するよう管理することができる。上記例はプロキシを通してロックにアクセスする１つのスレッドについて言及しているが、複数のスレッドが単一のプロキシを通して１つのノードにアクセスできるようにしてもよい。更に、スレッドが単一ノード上の複数の対応するプロキシを通して複数のロックにアクセスできてもよい。] 図２
[0028] クラスタ内の複数のノードは同質のものである必要がなく、ノードを構成するコンピュータのタイプ又は構成において、若しくは、該ノード上で実行する処理において、これらのリソースをマスター制御するために公平に負荷を分散化するために、該クラスタの複数メンバーノードの相対的能力に従い、様々なロックマスターを分散化することが望ましい。ノードの能力を決定するための要因としては、例えば、処理速度、ノード上のプロセッサの数、利用可能なメモリの大きさ、ノード上の所望の負荷、などを含んでいてよい。ノードの能力は自動的に検出できるようにしてもよいし、あるいは、当該クラスタの管理者が該能力を定義できるようにしてもよく、そして、該能力の情報が様々なノード間でのロックマスターの分散化を決定する際に使用できるようになっていてよい。]
[0029] 図３はロックマスターが１クラスタ内の様々なノード間でどのように分散されるかを示す図である。元のマスターマップ３１０は、複数のロックマスター１乃至ｃが４ノードからなるクラスタのメンバーにどのように対応付けられるかを図示している。図においては、ロックマスターが、該マスターに対応付けられたロックの名前に基づきノードにわたって均等に分散化されている。各ロックの名前（すなわちロック名）は、例えば、ｉノード（inode）、ロックタイプ又はボリュームのようなファイルシステム情報から、ユニークに決定される。] 図３
[0030] ロックマスターを分散化するための一手法は、ロック名のハッシュ（hashing）を使用する。該ロック用のホストマスターに対するノードＩＤ（ノード識別子）は、ハッシュ値（モジュロｎ）として決定される。ここで、ｎは当該クラスタ内のホストマスターにとって利用可能なノードの数である。もし１つのノード（例えばノード３）が該クラスタを離れたならば、新たなマスターマップ３２０が同じアルゴリズムを使用して生成される。従って、マスター用のホストＩＤはハッシュ値（モジュロｎ）に基づいているが故に、ロックマスターの多くは生き残ったノード間で再配置（relocate）される。再配置されるマスターの数は、「（（ｎ−１）／ｎ）＊ロックマスターの数」である。]
[0031] 図３に示されたシステムにおいては、ロックマスターの多くが再配置されるべきであるので、古いマスター情報は無効にし、各クラスタノード上に新しいマスターテーブルを再構築するのが妥当である。新たなマスターが再分散されると、生き残ったプロキシは種々の新マスターにロック状態を送る。そのようなシステムの１つの問題は、ロック数とクラスタのサイズが増加するにつれて、再分散されるべきマスターを待つと共にプロキシがロック状態を送るのを待つ間に、クラスタの利用不可能性の増加量が生ずることである。更に、ロック用のマスターホストＩＤを決定するための上述のアルゴリズムは、再分散化を実行する際の複数ノードの相対的能力を考慮に入れていない。更に、クラスタの再構成の後に、各ロックＩＤが再ハッシュされる必要があり、また、マスターホストＩＤが該クラスタ内の生き残りのノード数に照らして再計算される必要があるので、処理コストがかなりかかる。] 図３
[0032] バランスしたコンシステント・ハッシュ法
本発明の実施例は、バランスしたコンシステント・ハッシュ法の仕組みを使用して、マスターホストＩＤの決定に際しての計算を減少させるのみならず、当該クラスタ内の様々な生き残りノード間で再分散化されるべきマスターの数をも減少させる。リソース識別「空間（space）」は、それに対応付けられたマスターがクラスタ内で分散化されるべきである各リソース毎の識別子によって定義される。本発明の実施例は、クラスタ内の様々なロック名についてのハッシュ計算を実行し、そこからリソース識別空間の範囲を決定する。このリソース識別空間は、計算されたハッシュ値の最小値から最大値までの広がりを持つ。このリソース識別空間は、それから、クラスタメンバーノードの相対的能力に従い、複数のクラスタメンバーノード間で釣り合いよく振り分けられる。もし或るノードが当該クラスタから離れた又は加入したとするならば、リソース識別空間は、生き残りのクラスタメンバーノード間で再び釣り合いよく振り分けられる。]
[0033] 図４は、本発明の実施例に従い、よって使用可能な、分散ロックマネージャを提供する２つのレベルのロックマネージャ環境を簡略化して示す図である。リソース識別空間４１０は、計算されたハッシュ値の最小値から最大値までの、ロック識別子用のハッシュ値の分布を図で示している。図示の目的のために、ロックＡ乃至Ｌはリソース識別空間を通して均一に分布しているように示されているが、そのような均一の分布は必要とされない。更に、クラスタメンバーノード１乃至４の元のマッピング４２０が示されている。一例として、４ノードのクラスタが使用され、各ノードの相対的能力は同じであるとみなされている。従って、ロック管理ハッシュ空間の責任領域の各々は、４つのノード間で均等であるとされている。] 図４
[0034] バランスしていないマップ４３０は、ノード３がクラスタから離れた事例を図示している。該図示事例では、ノード２の責任領域が単にノード３の責任領域内に延長されており、これにより、ノード２がノード３によって元々実行されていた全てのロック管理の責任を持つようにされる。この事例は、ノード２が、ロック管理タスクを実行するために、他のどのノード１又は４より多くのリソースを出費する必要があるため、バランスしていないと考えられる。]
[0035] ロックマスターの再バランスしたマップ４４０は、生き残りの複数ノードにより均等に負荷を分け合わせるために、より望ましいものである。図示のように、ノード２がクラスタ内に残っていたとしても、ロックＤ用のマスターがノード２からノード１に移る。元々はノード３が行っていたロックＧ及びＨ用のマスターの責任は、今や、ノード２によって行われる。元々はノード３が行っていたロックＩ用のマスターの責任はノード４に移される。]
[0036] マップ４４０用の再バランス処理を実行する際、１２のロックマスターのうち４のみが、ノード３がクラスタを離脱した後に、再配置される。これは、図３に示されたシステムにおける９個（＝（（ｎ−１）／ｎ）＊ロックマスターの数）のマスターに比べて少ない。従って、４４０に示されたバランスしたコンシステント・ハッシュ法の仕組みを通して、リソースのかなりの量を、ロックマスターの再作成（この点は追って詳しく述べる）に要求される計算サイクルと、様々なプロキシが新たなロックマスターにその状態を送るために要求されるネットワークリソースとの両方において、大切に使うことができる。更に、ロック識別子が再ハッシュされないので、コンピュータリソースを更に節約することができる。] 図３
[0037] マスターされるノード及びリソースの数が増加するにつれて、再分散されるリソースマスターの数がリソースマスターの合計のほぼ１／３に漸近的に近づく。再分散されるリソースマスターの数は、また、リソース識別空間の「エッジ」の１つに責任を持つノードに対して該空間の中間に責任を持つノードが利用不能になるかにつき、敏感である。本発明の一実施例は、エッジ無しのリソース識別空間をモデルすることにより、このエッジ感度問題を解決する。すなわち、例えば、リソース識別空間４１０の「Ａ」エッジを該リソース識別空間の「Ｌ」エッジにリンクすることで、エッジ無しのリソース識別空間をモデルする。]
[0038] 別のバランスしたコンシステント・ハッシュ法は、クラスタを離脱したノードから生き残りノード群にロックマスターを単に移動することにより実現され得る。図４における一例を使用して説明すると、ノード３がクラスタを離脱した場合、ロックＧに対応するロックマスターをノード１に、Ｈをノード２に、Ｉをノード４に移動する。これは、移動されるマスターの数が１／ｎに等しくなることとなる。ここで、ｎは元のクラスタ中のノードの数である。] 図４
[0039] １組のクラスタメンバーノードからのマスターノードの選択は、利用可能なノードのアレイとリソース識別空間を使用して実行される。マスターノードＩＤアレイ（master_nid[idx]）は、各ノードの縮尺重み付け（scaled weight）に基づき複製されたクラスタメンバーノードＩＤの分類されたリストを含む。各ノードの縮尺重み付け（scaled weight）はアレイ内の他のノードに対する１つのノードの相対的能力に基づいている。例えば、もしノード１と３が１の重みを持ち、ノード２が２の重みを持つとすると、master_nidアレイはエントリ｛１，２，２，３｝を内容とするであろう。該アレイの合計重み（tot_weight）は、master_nidアレイのエントリの数である。そこで、上述の例では、tot_weightは４である。ロックリソース用のマスターは、該ロックの名前のハッシュ値を計算して該ハッシュ値をハッシュ値空間内の最大値（max_hash）で割り算し、その商を合計重みで掛け算し、その積をマスターノードＩＤ値をmaster_nidアレイから取り出すための指標（インデックス）として使用することにより、該master_nid内に表された１つのノードに対して割り当てられることができる。従って、master_nidアレイ用の指標に到達するための式は、
idx = (hashval/max_hash) * tot_weight
である。master_nidの指標のための上記式は、最大ハッシュ値に対するロック名のハッシュについての正規化された値を計算し、該正規化された値をmaster_nidアレイ内のエントリの合計数で乗算することであることが分かる。]
[0040] 本発明の一実施例において、master_nidアレイの指標を計算するために、変更例として、整数計算を使用してもよい。この実施例においては、指標は下記式で計算される。
idx = (hashval 11* tot_weight）>> 11
hashval 11は、該ロック名についての計算されたハッシュ値の最下位１１ビットである。hashval 11は、master_nidアレイの合計重みで乗算される。その計算結果は１１ビットだけ右シフトされ、指標値を産出する。この実施例では、該１１ビットと１１ビットの右シフトは、再配置の最中に探索されることができるハッシュ値の或る選択された最大値に関係して選択される。]
[0041] バランスしたコンシステント・ハッシュ法の代替的な仕組みは既に述べたものであり、クラスタに残されたノードに対応付けられたロックマスターだけが再配置され、クラスタ内の残りのノードに対応付けられたそれらのロックマスターはそれらのノーに保持され続ける。そのような一例はここに述べられている。上述したように、master_nidアレイはクラスタ内の各ノードの縮尺重み付けに基づくエントリ群を内容としている。新しいクラスタについて、又はノードが参入してきたクラスタについて、master_nidアレイは、レベル１のマッピングテーブルとして記憶される。この代替的な仕組みは、ノードがクラスタを離れるとき第２のレベルのマッピングテーブル（例えばレベル２のマッピングテーブル）を導入する。ノードがクラスタを離れるとき、もはや該クラスタ内にいないノードに対応するmaster_nidアレイ内のそれらのエントリは、ゼロ値によって置き換えられ、この変更されたmaster_nidアレイがレベル１のマッピングテーブルとして保持される。それから、レベル２のマッピングテーブルは、生き残るノードの縮尺重み付けに基づき構築される。レベル２のマッピングテーブルは、外れたノードからのマスターを生き残るノードに再分散するために使用される。マスターノードＩＤのルックアップ（参照）中に、レベル１のマッピングテーブル用の指標が上述した手法のいずれかによって計算される。もしレベル１のマッピングテーブル内のノードＩＤがゼロならば、第２の指標がレベル２のマッピングテーブル用に計算される。このレベル２の指標を計算するための式は次の通りである。
idx 2 = (((((hashval 11)&0x3f)<<5│((hashval 11)>>6)) * tot_weight2) >> 11
上記式において、hashval 11はハッシュ値の最下位１１ビットであり、tot_weight2はレベル２のマッピングテーブルのサイズである。再び、ハッシュ値の最下位１１ビットの使用と１１ビットの右シフトが、再配置されたマスターを探索するために使用されたテーブルサイズに関係する。]
[0042] 上述した本発明の代替的実施例では２つのレベルのマッピングテーブルを使用しているが、いくつのレベルのマッピングテーブルが使用されるようになっていてもよく、各レベルはクラスタ内のノードの数を変更するイベントに対応している。そのような使用するテーブルの数は、テーブルを記憶するのに必要なメモリ資源を必要とし、また、テーブル参照を複数レベルで実行する際に使用されるコンピュータ資源を必要とする。更に、上述したように、新しいノードがクラスタに参入するとき、レベル１のマッピングテーブルが構築される。従って、上述した実施例では、既存のノードがクラスタを離脱するのと同じ期間において新しいノードがクラスタに参入するとき、レベル１のマッピングテーブルだけが構築される。]
[0043] 図４に示された例は、ネットワーク環境からのノードの取り除きをもたらし、引き続く残りのノードに対するリソース管理の再分散化処理をもたらし、その方法論は、ネットワーク環境に対するノードの追加を含み、且つ、追加ノードに対するリソース管理責任の分散化を許す。] 図４
[0044] 図５ａは、本発明の実施例に従い、マッピングテーブル再構築プロセス中にクラスタノードによって実行されるタスクの一実施例を簡略化して示すフロー図である。ロックマスター分散化は、クラスタのメンバーシップの変化によってトリガーされる再スタートコール（要求）によって始められる（５１０）。そのようなクラスタのメンバーシップの変化は、クラスタ・メンバーシップ・モニターによって検出され、クラスタに参入した新たなメンバーシップ識別子の出現又は或る時間経過後に該クラスタから或るノードが不在となること又は或るノードからの明示的な離脱表明によって識別される。再スタートコールに応じて、該クラスタ内の各ノードは当該ノードについての情報を全ての他のノードにブロードキャスト（同報配信）する（５１５）。そのようなノード情報は、例えば、上述したようなノード能力情報と、該クラスタに該ノードが参入したときを示す情報（例えばノード参入タイムスタンプ）である。それから、該ノードはその他の残りの全てのノードからノード情報を受信するのを待つ（５２０）。] 図５ａ
[0045] 該他のノードから受信する前記情報に照らして、上述したように、各ノードはレベル１のマッピングテーブル又はレベル２のマッピングテーブルを構築する（５２５）。各ノードに記憶されたプロキシテーブルがスキャンされ、上述したバランスしたコンシステント・ハッシュ法を使用して新たなマッピングテーブルを参照し且つプロキシ用の以前のマスターの記録（例えばリモートマスターテーブル）と該新たなマッピングテーブルに対する参照結果とを比較することにより、いずれかのプロキシが再配置されたマスターに関係しているかどうかが決定される（５３０）。再配置されたマスターがなければ（５３５）、該ノード上のプロキシはそれに対応付けられたマスターに情報を送る必要がない。これは、上述したような従来技術において殆ど全てのマスターが再配置され且つそれ故にマスターテーブルが完全に再構築され、全てのプロキシがそれらのマスターに情報を送らねばならない、という従来技術に比べて、バランスしたコンシステント・ハッシュ法の顕著な特徴である。もしプロキシがそれに対応付けられた再配置されたマスターをもっているならば（５３５）、今やロックＩＤを支配する責任を持つようになったノードに対してリマスター（マスター組み直し）メッセージが送信される（５４０）。これは再配置されたマスターを持つ各プロキシ毎に実行される。１つのノードは、該ノードがリマスターメッセージを送ることを完了したということを、例えば、該ノードがリマスターメッセージを送ることを終了したということを示すメッセージを該クラスタ内の全てのノードにブロードキャストすることにより、示すことができる（例えば「DONE_REMASTER」メッセージ）。]
[0046] 図６は、本発明の実施例に従い、クラスタ環境におけるプロキシと再配置されたマスターとの間のリマスターメッセージのやり取りを簡略化して示すブロック図である。図６は、クラスタのメンバーがノード６１０〜６６０であることを図示している。ノード６１０はロックマスターＡに責任を持つ。ロックマスターＡがノード６１０に再配置されたことを発見すると、ロックＡのプロキシを持つクラスタ内の各ノードはリマスターメッセージをノード６１０に通信する。同様に、ノード６３０はロックマスターＢに責任を持ち、ロックＢのプロキシを持つノードがノード６３０にリマスターメッセージを送信する。この図から、再配置されたロックマスターの数が多いほど，リマスターメッセージのためにネットワーク通信量が多い。更に、ノード及びプロキシの数が増加するにつれ、ネットワーク通信量も増加する。そこで、ロックマスターの再配置を最小に保つ仕組みが、ネットワークリソース（例えば帯域）を有意義に維持するであろう。] 図６
[0047] 図５ａに戻ると、該ノードは、該ノードから再配置されたいずれかのマスターを該ノードのマスターテーブルから削除する（５４５）。該ノードが、該ノード自身のマスターテーブルを変更し、該変更されたマスターテーブルに関連する待ち行列（queue:キュー）上のハウスキーピング・タスクを実行した後（例えば、図５ｂに関連して以下述べる）、該ノードのプロキシに対応付けられた各再配置されたマスター毎に、ノードのプロキシからのいずれかの未処理のリクエストが該再配置されたマスターに送信され得る（５５０）。] 図５ａ 図５ｂ
[0048] 図５ｂは、本発明の実施例に従い、変更されたマスターテーブルに関連するハウスキーピング・タスクにおいて実行されるタスクを簡略化して示すフロー図である。該ノードが全ノードからの全てのリマスターメッセージを受信したかどうかの判定がなされる（５６０）。そのような判定は、例えば、該ノードが上述のような「DONE_REMASTER」メッセージを全ての他のノードから受信したかどうかを判定することにより、行うことができる。もしそうでなければ、該ノードは追加のリマスターメッセージを待つことができる。もし全てのリマスターメッセージを受信したならば、該ノードは、該ノードによって支配（マスター）されているロック処理のリクエストを取り扱う「準備」ができたことを表明する情報をブロードキャストする（５６５）。それから、該ノードは該クラスタ内の他の全てのノードから「準備」表明情報を受信するよう待機することができ（５７０）、そのようにしているとき、該ノード上のマスターテーブルをクリーンアップすることに関連したタスクを実行することができる。該ノードは、例えば、リクエストの待ち行列をスキャンして、該クラスタから離脱したノードからのロックリソースのリクエストを削除することができる（５７５）。該ノードは、許可の待ち行列をスキャンして、該クラスタから離脱したノードに与えられた許可を削除することができる（５８０）。許可が削除された場合（５８５）、該ノードはリクエストの待ち行列を処理して、該許可の削除に照らして、いずれかのリクエストされたロックリソースが今や許可され得るかどうかを判定することができる（５９０）。それ以外の（他のスレッドによって）ロックされたリソースを無効にするためのリクエストについての無効待ち行列がスキャンされることができ、もし無効のリクエスト元が該クラスタから取り除かれているならば、許可の待ち行列に昇進される代わりに全ての無効が終了させられるとき、そのエントリが削除されることができる（５９５）。] 図５ｂ
[0049] 図示では順次に行われるようにしているが、これらのタスクの多く（例えばプロキシテーブルスキャン（５３０）、再配置されたマスターの削除（５４５）、リクエスト及び許可待ち行列のスキャン（５７５，５８０）、マスターテーブルのアップデート（下記の７１５））が１つのノードによって同時的に実行されることができ、それにより、メンバーノード間でのマスターの再配置に関わり合う時間量を減少させることができる。]
[0050] 新たなマスターテーブルを実装するための処理の一部は、古いメッセージを除去することを含んでいる。古いメッセージは、再配置されたか廃棄されたマスターからノードにあるいはその逆に発せられたものである。古いメッセージは、また、もはや該クラスタのメンバーではない送り手のノードからも廃棄され得る。更に、該クラスタに参入した送り手又は受け手に送られたいかなるメッセージも、同様に、廃棄され得る。]
[0051] 図７は、本発明の実施例に従い、ロックマスター再分散化中に複数クラスタノードについての新たなマスターをセットアップする場合に実行されるいくつかのタスクを簡略化して示すフロー図である。ノードは、５４０において送られるもののようなリマスターメッセージを受信したとき処理を開始する（７１０）。それから、該ノードは、該ノードが責任を持つべき新たなマスターについてのエントリを含むように、該ノードのマスターテーブルをアップデートする（７１５）。] 図７
[0052] ネットワーククラスタ環境におけるリソース管理の再分散化は、ロックリソース管理の一例を使用して、上述された。しかし、本発明のコンセプトは、リソースが共有される分散コンピュータ環境内でのその他のタイプのリソースの分散化管理に対しても適用することができることが理解されるべきである。本発明の原理は、ロック管理に限らず、例えば、分散コンピュータ環境内でのアプリケーションの管理あるいは各電子メールサーバが１つのネットワークについての受取人の電子メールアドレスの範囲に責任を持つような複数の電子メールサーバを提供することにも適用することができる。]
[0053] コンピュータ及びネットワーク環境の一例
上記のように、本発明は、多様なコンピュータシステムとネットワークを使用して実装され得る。そのようなコンピュータシステムとネットワーク環境の一例が図８及び図９を参照して以下説明される。] 図８ 図９
[0054] 図８は本発明を実装するのに適したコンピュータシステム８１０のブロック図を示す。ネットワークコンピュータシステム８１０は該コンピュータシステム８１０の主要なサブシステムを相互接続するバス８１２を含み、該主要なサブシステムとは、中央プロセッサ８１４、システムメモリ８１７（典型的にはＲＡＭ、しかしＲＯＭやフラッシュＲＡＭその他を含んでいてもよい）、入出力コントローラ８１８、オーディオ出力インタフェイス８２２を介在させたスピーカシステム８２０のような外部オーディオ装置、ディスプレイアダプター８２６を介在させたディスプレイ画面８２４のような外部装置、シリアルポート８２８、８３０、キーボード８３２（キーボードコントローラ８３３でインタフェイスされている）、記憶装置インタフェイス８３４、フレキシブル磁気ディスク８３８を受容するよう動作するフレキシブル磁気ディスクドライブ８３７、光ファイバーチャンネルネットワーク８９０に接続するよう動作するホストバスアダプター（ＨＢＡ）インタフェイスカード８３５Ａ、ＳＣＳＩバス８３９に接続するよう動作するホストバスアダプター（ＨＢＡ）インタフェイスカード８３５Ｂ、光ディスク８４２を受容するよう動作する光ディスクドライブ８４０等である。また、マウス８４６（若しくはシリアルポート８２８を介してバス８１２に接続されたその他のポイント及びクリック装置）、モデム８４７（シリアルポート８３０を介してバス８１２に接続された）、ネットワークインタフェイス８４８（バス８１２に直接結合された）などが含まれる。] 図８
[0055] バス８１２は中央プロセッサ８１４とシステムメモリ８１７との間でのデータ通信を可能にし、既に述べたように該システムメモリ８１７は読み出し専用メモリ（ＲＯＭ）又はフラッシュメモリ（両方共図示せず）、ランダムアクセスメモリ（ＲＡＭ）（図示せず）を含む。ＲＡＭは、一般に、オペレーティングシステムとアプリケーションプログラムがロードされるメインメモリである。ＲＯＭ又はフラッシュメモリは、その他のコードの間で、周辺機器要素との相互作用のような基本的ハードウェア操作をコントロールする基本的入力−出力システム（ＢＩＯＳ）を含み得る。コンピュータシステム８１０に常駐するアプリケーションは、一般に、ハードディスクドライブ（例えば固定ディスク８４４）、光ディスクドライブ（例えば光ディスクドライブ８４０）、フレキシブル磁気ディスクユニット８３７又はその他の記憶媒体のような、コンピュータ読み取り可能な媒体上に記憶されアクセスされる。加えて、アプリケーションは、ネットワークモデム８４７又はインタフェイス８４８を介してアクセスされるとき、アプリケーション及びデータ通信技術に従って変調された電子的信号の形態をとり得る。]
[0056] 記憶装置インタフェイス８３４は、コンピュータシステム８１０のその他の記憶装置インタフェイスの場合のように、固定ディスクドライブ８４４のような情報の記憶と取り出しのための標準的なコンピュータ読み取り可能な媒体に接続され得る。固定ディスクドライブ８４４は、コンピュータシステム８１０の一部であってもよく、あるいは、別であって他のインタフェイスシステムを介してアクセスされるようになっていてもよい。モデム８４７は、電話リンクを介してリモートサーバーに又はインターネットサービスプロバイダ（ＩＳＰ）を介してインターネットに、ダイレクトに接続を提供し得る。ネットワークインタフェイス８４８は、ダイレクトネットワークリンクを介してリモートサーバーに又はＰＯＰ（point of presence）を介してインターネットに、ダイレクト接続を提供し得る。ネットワークインタフェイス８４８は、デジタル携帯電話接続、携帯電話デジタルパケットデータ（ＣＤＰＤ）接続、デジタル衛星データ接続、その他のような無線技術を使用して、それらの接続を提供してもよい。]
[0057] 多くのその他の装置又はサブシステム（図示せず）（文書スキャナーやデジタルカメラその他）が同様の手法で接続されていてもよい。反対に、図８に示した全ての装置が本発明を実施するために提示される必要がない。装置又はサブシステムは、図８とは異なるやり方で相互接続されることができる。図８に示すようなコンピュータシステムの動作は、公知であり、本書では詳しく述べない。本発明を実現するためのコードは、システムメモリ８１７、固定ディスク８４４、光ディスク８４２、又はフレキシブル磁気ディスク８３８の１以上のようなコンピュータ読み取り可能な記憶媒体内に記憶されることができる。コンピュータシステム８１０上に提供されたオペレーティングシステムは、ＭＳ−ＤＯＳ（登録商標）、ＭＳ−ＷＩＮＤＯＷＳ（登録商標）、ＯＳ／２（登録商標）、ＵＮＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標）、又はその他公知のオペレーティングシステムであってよい。] 図８
[0058] 更に、ここで説明した信号に関しては、この技術の熟練者であれば、信号が第１ブロックから第２ブロックにダイレクトに送信されることができ、若しくは信号がブロック間で変形される（例えば増幅、減衰、遅延、ラッチ、バッファ、インバート変換、フィルター、又はその他の変更）ことができる、と理解するであろう。上記実施例の信号は１ブロックから次に送信されるようになっているが、本発明の別の実施例では、該信号の情報としての及び／又は機能的な観点においてブロック間で送信がなされる限り、そのような直接の送信に代えて、変更された信号が含まれていてよい。いくつかの拡張において、第２のブロックで入力された信号は、関係する回路の物理的限界（例えば減衰や遅延が不可避である）のために、第１のブロックから出力された第１の信号から派生された第２の信号として概念化され得る。そこで、ここで使用されるように、第１の信号から派生された第２の信号は、回路限界であるにせよ、あるいは該第１の信号の情報としての及び／又は機能的な観点を変更しない他の回路要素を通過するにせよ、該第１の信号又は該第１の信号の何らかの変形を含む。]
[0059] 図９はネットワークアーキテクチャ９００を図示するブロック図であり、クライアントシステム９１０，９２０，９３０及び記憶サーバー９４０Ａ，９４０Ｂ（これらのいずれかは前記コンピュータシステム８１０を使用して実装され得る）がネットワーク９５０に結合される。記憶サーバー９４０Ａが更に記憶装置９６０Ａ（１）〜９６０Ａ（Ｎ）を直接的に附属しており、かつ、記憶サーバー９４０Ｂが更に記憶装置９６０Ｂ（１）〜９６０Ｂ（Ｎ）を直接的に附属しているように図示されている。記憶エリアネットワーク（ＳＡＮ）に対する接続は本発明の動作に必須のことではないが、記憶サーバー９４０Ａ，９４０Ｂは、また、ＳＡＮ組織９７０に接続されてもいる。ＳＡＮ組織９７０は、記憶サーバー９４０Ａ，９４０Ｂによる、ひいてはネットワーク９５０を介したクライアントシステム９１０，９２０，９３０による、記憶装置９８０（１）〜９８０（Ｎ）へのアクセスをサポートする。またＳＡＮ組織９７０を介してアクセス可能な特定の記憶装置の一例として、インテリジェント記憶アレイ９９０が図示されている。] 図９
[0060] コンピュータシステム８１０、モデム８４７、ネットワークインタフェイス８４８、若しくはその他いくつかの手法を使用して、クライアントコンピュータシステム９１０，９２０，９３０の各々からネットワーク９５０への接続性を提供することができる。クライアントシステム９１０，９２０，９３０は、例えばウェブブラウザやその他のクライアントソフトウェア（不図示）を使用して、記憶サーバー９４０Ａ，９４０Ｂ上の情報にアクセスすることができる。そのようなクライアントソフトウェアは、記憶サーバー９４０Ａ又は９４０Ｂ、若しくは記憶装置９６０Ａ（１）〜９６０Ａ（Ｎ）、９６０Ｂ（１）〜９６０Ｂ（Ｎ）、９８０（１）〜９８０（Ｎ）の１つ、若しくはインテリジェント記憶アレイ９９０、によってホストされるデータに、クライアントシステム９１０，９２０，９３０がアクセスできるようにするものである。図９はデータを交換するためのインターネットのようなネットワークでの使用を図示しているが、本発明はインターネット又は特定のネットワークベースの環境に限定されるものではない。] 図９
[0061] その他の実施例
本発明は、上述した利点及びその他の本来的にその中に持つ利点を奏するのに適している。上記では、本発明が説明され、図示され、かつ、発明の特定の実施例を参照して定義されているが、そのような参照は発明を限界づける意味合いを持つのではなく、そのような限界を暗示するものではない。本発明は、関係する当該技術分野の通常の熟練技術者にとって、かなりの変形と変更とその形態及び機能における等価物が可能である。ここで述べかつ図示した実施例は一例にすぎず、発明の範囲を網羅するものではない。]
[0062] 上述の実施例では、他の構成要素（例えばコンピュータシステム８１０の構成要素として示された種々の要素）内に含まれる構成要素を含んでいる。そのような設計思想は単なる一例であり、実際のところ、その他の多くの設計思想が上述と同様の機能を実現するために実装され得る。一般的に言えば、しかし、明白な趣旨で、同様の機能性を達成するためのどのような構成要素の配列であっても、所望の機能性を達成するように有効に「対応付け」られる。従って、特定の機能性を達成するためにここに組み合わされた任意の２つの構成要素は、設計思想又は中間の構成要素と関係なく、所望の機能性が達成されるように互いに「対応付け」られた（関連付けられた）ものと見られ得る。同様に、そのように対応付けられた任意の２つの構成要素は、所望の機能性を達成するために互いに対して「操作可能に接続された」または「操作可能に結合された」ものとしても見なし得る。]
[0063] 上述の詳細な説明ではブロック図、フロー図及び実例を使用して本発明の様々な実施例を説明した。各ブロック図、フロー図の各ステップ、動作、及び／又は実例の使用によって説明された構成要素が、個別に及び／又は一括して、広範囲なハードウェア、ソフトウェア、ファームウェア又はそれらの任意の組み合わせによって実装され得ることは、当業者に理解されるであろう。]
[0064] 本発明は完全に機能的なコンピュータシステムの脈絡で説明されてきたが、当業者は、本発明が様々な形態のコンピュータプログラム製品として分配され得ること、及び本発明が分配を実際に遂行するために使用される信号保持媒体の特定のタイプとは無関係に等しく適用されることを理解するであろう。信号保持媒体の例は、将来的に発達する媒体記憶及び分配システムは勿論のこと、コンピュータ読み取り可能な媒体、デジタル又はアナログ通信リンクのような伝送型媒体などがある。]
[0065] 上述の実施例は特定のタスクを実行するソフトウェアモジュールによって実装され得る。ここで述べたソフトウェアモジュールは、スクリプト又はバッチ若しくはその他の実行可能なファイルを含んでいてよい。該ソフトウェアモジュールは、フレキシブル磁気ディスク、ハードディスク、半導体メモリ（例えばＲＡＭ，ＲＯＭ，フラッシュ型メディア）、光ディスク（例えばＣＤ−ＲＯＭ、ＣＤ−Ｒ，ＤＶＤ）又はその他のタイプのメモリモジュールのような、機械読み取り可能な又はコンピュータ読み取り可能な記憶媒体上に格納されていてよい。本発明の実施例に従ってファームウェア又はハードウェアモジュールを記憶するために使用される記憶装置は、半導体ベースのメモリを含んでいてよく、該メモリは、永久的に、取り外し可能に、又は遠隔的に、マイクロプロセッサ／メモリシステムに結合されるものであってよい。こうして、該モジュールは、コンピュータシステムが当該モジュールの機能を実行するように該コンピュータシステムを構成するためのコンピュータシステムメモリ内に格納され得る。その他の新規な及び様々なタイプのコンピュータ読み取り可能な記憶媒体が、ここに述べたようなモジュールを記憶するために使用されてよい。]
[0066] 上記説明は本発明を説明するために意図されており、限界づけるものとして取られるものではない。本発明の範囲内の別の実施例が可能である。当業者はここで述べた構造及び方法を提供するために必要な手順を容易に実装するであろうし、手順の処理パラメータ及び順序は、説明のためのみに与えられたものであり、本発明の範囲内の変形例と同様に、所望の構造を達成するために変化され得る。ここに述べた実施例の変化と変更は、本発明の範囲から逸脱することなく、ここに述べた説明に基づきなされ得る。]
[0067] 従って、本発明は、全ての関連において均等物への完全な認識を与える添付の特許請求の範囲によってのみ限定されるものである。]

权利要求:

請求項1
リソース識別空間における複数のリソース識別子の配置を判定するステップと、前記リソース識別空間を第１の複数の個別の責任領域に分割するステップと、ここで、前記責任領域の各々が１つの独特のネットワークノードに対応付けられていて、全責任領域の合計が前記リソース識別空間の全てを包含しており、第１の責任領域内に配置された１つのリソース識別子に対応付けられた１つのリソースに対する管理責任を、前記第１の責任領域に対応付けられた前記ネットワークノードに割り当てるステップとを具備する方法。
請求項2
前記リソース識別空間は名前空間である、請求項１に記載の方法。
請求項3
１つのリソースの名前をハッシュすることにより、前記複数のリソース識別子のうちの１つのリソース識別子を計算するステップを更に具備する請求項２に記載の方法。
請求項4
ｉノード識別子を使用して前記１つのリソースの名前を引き出すステップを更に具備し、ここで、該リソースは、ファイルシステム内の１つのファイル及び１つの記憶位置のうち１つである、請求項３に記載の方法。
請求項5
電子メールアドレスを使用して前記１つのリソースの名前を引き出すステップを更に具備し、ここで、該リソースは、メールボックス、該メールボックスに関連付けられた状態情報、該メールボックスに関連付けられたメタデータ、該メールボックスに関連付けられた管理情報、及び電子メールシステム内のメールデータのうち１つである、請求項３に記載の方法。
請求項6
前記ネットワークノードの各々は、ネットワークノードの１クラスタ内の１メンバーである、請求項１に記載の方法。
請求項7
前記複数のリソース識別子のうちの１つによって識別される１つのリソースが前記ネットワークノードの１クラスタ内の全メンバーにアクセス可能である、請求項１に記載の方法。
請求項8
前記対応付けられたネットワークノードの能力に基づき該対応付けられたネットワークノードに対する責任領域を決定するステップを更に具備する請求項１に記載の方法。
請求項9
前記対応付けられたネットワークノードの能力を、プロセッサ能力とメモリ能力のうち１以上に関係付けるステップを更に具備する請求項８に記載の方法。
請求項10
前記対応付けられたネットワークノードの能力を、ユーザ入力によって定義するステップを更に具備する請求項８に記載の方法。
請求項11
前記対応付けられたネットワークノードの能力は、各他のネットワークノードに対して相対的に定義される、請求項８に記載の方法。
請求項12
１つのネットワークノードがネットワークに参入又は離脱するとき、責任領域に対応付けするのに利用可能なネットワークノードの現在の数を使用して、前記分割するステップと前記割り当てるステップを第２の複数の責任領域において実行するステップを更に具備する請求項１に記載の方法。
請求項13
前記第１の複数の責任領域と前記第２の複数の責任領域の間での責任領域の重複を最大にするステップを更に具備する請求項１２に記載の方法。
請求項14
リソース識別空間における複数のリソース識別子の配置を判定するように構成された、プロセッサによって実行可能な、第１の命令セットと、前記リソース識別空間を第１の複数の個別の責任領域に分割するように構成された、プロセッサによって実行可能な、第２の命令セットと、ここで、前記責任領域の各々が１つの独特のネットワークノードに対応付けられていて、全責任領域の合計が前記リソース識別空間の全てを包含しており、第１の責任領域内に配置された１つのリソース識別子に対応付けられた１つのリソースに対する管理責任を、前記第１の責任領域に対応付けられた前記ネットワークノードに割り当てるように構成された、プロセッサによって実行可能な、第３の命令セットとを記憶したコンピュータ読み取り可能な記憶媒体。
請求項15
前記リソース識別空間は名前空間である、請求項１４に記載のコンピュータ読み取り可能な記憶媒体。
請求項16
１つのリソースの名前をハッシュすることにより、前記複数のリソース識別子のうちの１つのリソース識別子を計算するように構成された、プロセッサによって実行可能な、第４の命令セットを更に具備する請求項１５に記載のコンピュータ読み取り可能な記憶媒体。
請求項17
前記対応付けられたネットワークノードの能力に基づき該対応付けられたネットワークノードに対する責任領域を決定するように構成された、プロセッサによって実行可能な、第４の命令セットを更に具備する請求項１に記載のコンピュータ読み取り可能な記憶媒体。
請求項18
複数のネットワークノードと、ここで、該複数のネットワークノード内の各ネットワークノードは、それぞれに対応するプロセッサと、該プロセッサに結合されたメモリと、該プロセッサに結合されたネットワークインタフェイスとを備えており、前記複数のネットワークノードを互いに結合するように構成されたネットワークであって、前記ネットワークノードの前記ネットワークインタフェイスに結合される前記ネットワークとを具備し、前記各ネットワークノードの前記メモリが、リソース識別空間における複数のリソース識別子の配置を判定するように構成された、前記ネットワークノードの前記プロセッサによって実行可能な、第１の命令セットと、前記リソース識別空間を第１の複数の個別の責任領域に分割するように構成された、前記ネットワークノードの前記プロセッサによって実行可能な、第２の命令セットと、ここで、前記責任領域の各々が１つの独特のネットワークノードに対応付けられていて、全責任領域の合計が前記リソース識別空間の全てを包含しており、第１の責任領域内に配置された１つのリソース識別子に対応付けられた１つのリソースに対する管理責任を、前記第１の責任領域に対応付けられた前記ネットワークノードに割り当てるように構成された、前記ネットワークノードの前記プロセッサによって実行可能な、第３の命令セットとを記憶していることを特徴とするシステム。
請求項19
１つのリソースの名前をハッシュすることにより、前記複数のリソース識別子のうちの１つのリソース識別子を計算するように構成された、前記ネットワークノードの前記プロセッサによって実行可能な、第４の命令セットを更に具備する請求項１８に記載のシステム。
請求項20
前記対応付けられたネットワークノードの能力に基づき該対応付けられたネットワークノードに対する責任領域を決定するように構成された、前記ネットワークノードの前記プロセッサによって実行可能な、第４の命令セットを更に具備する請求項１８に記載のシステム。
請求項21
リソース識別空間における複数のリソース識別子の配置を判定するための手段と、前記リソース識別空間を第１の複数の個別の責任領域に分割するための手段と、ここで、前記責任領域の各々が１つの独特のネットワークノードに対応付けられていて、全責任領域の合計が前記リソース識別空間の全てを包含しており、第１の責任領域内に配置された１つのリソース識別子に対応付けられた１つのリソースに対する管理責任を、前記第１の責任領域に対応付けられた前記ネットワークノードに割り当てるための手段とを具備する装置。